package top;

/**
 * @author chenyw
 * @date 2022/7/12 9:54
 * @description     加油站
 */
public class Top134canCompleteCircuit {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int resC = 0;
            int resG = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                resC += cost[j];
                resG += gas[j];
                if (resC > resG) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                //i最远只能到达i+cnt则说明[i, i+cnt]区间内的所有点最远也只能到i + cnt;
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}
